def quick_sort(arr):
    if len(arr) <= 1:
        return arr

    # 选择基准元素（这里选择最后一个元素）
    pivot = arr[-1]
    # 分区：小于基准的元素放在左侧，大于基准的元素放在右侧
    left = [x for x in arr[:-1] if x <= pivot]
    right = [x for x in arr[:-1] if x > pivot]
    # 递归排序并合并
    return quick_sort(left) + [pivot] + quick_sort(right)

arr = [3, 6, 8, 10, 1, 2, 1]
sorted_arr = quick_sort(arr)
print(sorted_arr)  # 输出: [1, 1, 2, 3, 6, 8, 10]


import random

class Solution(object):#快速选择算法（找出无序数组第k大的值）
    def findKthLargest(self, nums, k):
        def partition(left, right):
            # 随机选择枢轴避免最坏情况
            pivot_index = random.randint(left, right)
            nums[pivot_index], nums[right] = nums[right], nums[pivot_index]
            
            pivot = nums[right]
            i = left
            for j in range(left, right):
                # 注意：这里改为小于等于，因为我们找第k大
                if nums[j] <= pivot:
                    nums[i], nums[j] = nums[j], nums[i]
                    i += 1
            nums[i], nums[right] = nums[right], nums[i]
            return i
        
        def quick_select(left, right, target_index):
            if left == right:
                return nums[left]
                
            pivot_index = partition(left, right)
            
            if pivot_index == target_index:
                return nums[pivot_index]
            elif pivot_index < target_index:
                return quick_select(pivot_index + 1, right, target_index)
            else:
                return quick_select(left, pivot_index - 1, target_index)
        
        # 第k大元素在排序后数组中的位置
        target_index = len(nums) - k
        return quick_select(0, len(nums) - 1, target_index)